package question.solution188;

import question.SolutionTemplate;

import java.util.HashSet;
import java.util.Set;

public class Solution188 implements SolutionTemplate {

    /***
     * dp[i][k][0] = Max(dp[i-1][k][1]+c[i], dp[i-1][k][0])
     * dp[i][k][1] = Max(dp[i-1][k-1][1]-c[i], dp[i-1][k][1])
     *
     * dp[-1][k][0] = dp[i][0][0] = 0
     * dp[-1][k][1] = dp[i][0][1] = Integer.MIN_VALUE
     *
     *
     */
    public int maxProfit(int k, int[] prices) {
        int[][][] maxRecord = new int[prices.length][k+1][2];
        boolean[][][] calculated = new boolean[prices.length][k+1][2];
        Set<String> testData = new HashSet<>();
        dp(prices.length-1, k, 0,maxRecord,calculated,prices,testData);
        //todo 计算结果有问题，k可化简
        System.out.println(testData);
        return 0;
    }

    private int dp(int i, int k, int m, int[][][] maxRecord, boolean[][][] calculatedMark, int[] prices, Set<String> testData){
//        testData.add(i+","+k+","+m);
        if(m == 0){
            if(i == -1){
                testData.add(i+","+k+","+m);
                return 0;
            }
            if(k == 0){
                maxRecord[i][k][m] = 0;
                calculatedMark[i][k][m] = true;
                testData.add(i+","+k+","+m);
                return 0;
            }
        }
        if(m == 1){
            if(i == -1){
                testData.add(i+","+k+","+m);
                return Integer.MIN_VALUE;
            }
            if(k == 0){
                maxRecord[i][k][m] = Integer.MIN_VALUE;
                calculatedMark[i][k][m] = true;
                testData.add(i+","+k+","+m);
                return Integer.MIN_VALUE;
            }
        }
        if(calculatedMark[i][k][m]){
            return maxRecord[i][k][m];
        }else{
            int max;
            if(m == 0){
                int dp1 = dp(i-1,k,1,maxRecord,calculatedMark,prices,testData);
                if(dp1 == Integer.MIN_VALUE){
                    max = dp(i-1,k,0,maxRecord,calculatedMark,prices,testData);
                }else{
                    max = Math.max(dp(i-1,k,1,maxRecord,calculatedMark,prices,testData)+prices[i], dp(i-1,k,0,maxRecord,calculatedMark,prices,testData));
                }
            }else{
                int dp1 = dp(i-1,k-1,1,maxRecord,calculatedMark,prices,testData);
                if(dp1 == Integer.MIN_VALUE){
                    max = dp(i-1,k,1,maxRecord,calculatedMark,prices,testData);
                }else{
                    max = Math.max(dp(i-1,k-1,1,maxRecord,calculatedMark,prices,testData)-prices[i], dp(i-1,k,1,maxRecord,calculatedMark,prices,testData));
                }
            }
            maxRecord[i][k][m] = max;
            calculatedMark[i][k][m] = true;
            return max;
        }
    }

    @Override
    public void test() {
        int[] prices = {2,4,1};
        int result = maxProfit(2,prices);
        System.out.println(result);
    }
}
